package code;

public class ReverseLinkedListII {
	
	static public class ListNode{
		int val;
		ListNode next;
		ListNode(int x) {
	        val = x;
	        next = null;    
		}
	}
	public ListNode reverseLinkedList(ListNode head){
		ListNode p,pre1,pre2;
		pre1=head;
		p=head;
		while(p!=null){
			pre2=pre1;
			pre1=p;
			p=p.next;
			if(pre2==pre1){
				pre2.next=null;
			}
			else pre1.next=pre2;
		}
		head=pre1;
		return head;
	}
    public ListNode reverseBetween(ListNode head, int m, int n) {
    	int cnt;
    	ListNode p,start,end,beforeStart = null,afterEnd = null,pre1,pre2;
    	end=null;
    	start=head;
    	p=head;
    	pre1=head;
    	cnt=1;
    	if(n==m || head==null)	return head;
    	while(p!=null){
    		pre2=pre1;
    		pre1=p;
    		p=p.next;
    		if(cnt==m){
    			start=pre1;
    			beforeStart=pre2;
    			if(pre1!=pre2)
    				pre2.next=null;
    		}
    		else if(cnt==n){
    			end=pre1;
    			afterEnd=end.next;
    			pre1.next=null;
    		}
    		cnt++;
    	}
//    	System.out.println(start.val+" "+end.val);
    	
    	if(start==head){
    		
    		head=reverseLinkedList(head);
    		start.next=afterEnd;
    	}
    	else{
    		end=reverseLinkedList(start);
    		beforeStart.next=end;
    		start.next=afterEnd;
    	}
//    	p=head;
//    	while(p!=null){
//    		System.out.print(p.val+" ");
//    		p=p.next;
//    	}
//    	System.out.println();
        return head;
    }
    public static void main(String[] args){
    	ReverseLinkedListII rl=new ReverseLinkedListII();
    	ListNode head=new ListNode(1);
    	ListNode a=new ListNode(2);
    	ListNode b=new ListNode(3);
    	ListNode c=new ListNode(4);
    	ListNode d=new ListNode(5);
    	head.next=a;
    	a.next=b;
    	b.next=c;
    	c.next=d;
    	
    	rl.reverseBetween( head, 1, 4);
    }
}
